package ai;

import org.jcp.xml.dsig.internal.dom.DOMUtils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

/*
* 多项式运算
* 可以用一个Map来维护所有的拆分
* */
public class 多项式运算 {

    //13x^3+5x+6
    //4x^2+3x+4

    public static void main(String[] args){
        //两个多项式和运算符
        String polynomial1;
        String operator;
        String polynomial2;

        //读取
        Scanner scanner = new Scanner(System.in);

        HashMap<Integer, Double> polynomialMap1;
        HashMap<Integer, Double> polynomialMap2;

        polynomial1 = scanner.next();
        operator = scanner.next();
        polynomial2 = scanner.next();

        polynomialMap1 = parseString(polynomial1);
        polynomialMap2 = parseString(polynomial2);

        switch (operator) {
            case "+":
                System.out.println(add(polynomialMap1, polynomialMap2, true));
                break;
            case "-":
                System.out.println(add(polynomialMap1, polynomialMap2, false));
                break;
            case "*":
                System.out.println(multiplication(polynomialMap1, polynomialMap2));
                break;
            case "/":
                System.out.println(div(polynomialMap1, polynomialMap2));
                break;
            default:
                System.out.println("输入有误");
                break;
        }
    }

    /*
    * 从多项式数组转化成Map类型的变量
    * */
    private static HashMap<Integer, Double> parseString(String ss) {
        HashMap<Integer, Double> result = new HashMap<>();

        ss.replace("-", "+-");
        String[] splitAdd1 = ss.split("\\+");

        for (String s : splitAdd1) {
            String[] temp = s.split("\\^");

            //没有指数的形式
            if (temp.length <= 1) {
                //如果没有指数有x，则是一次项
                if (temp[0].contains("x")) {
                    int index = 1;
                    double value;
                    try{
                        value = Double.parseDouble(temp[0].replace("x", ""));
                    }catch (Exception e) {
                        value = 1;
                    }

                    if (result.containsKey(index)) {
                        value += result.get(index);
                    }
                    result.put(index, value);
                } else { //没有指数且没有x，是常数项
                    int index = 0;
                    double value = Double.parseDouble(temp[0]);
                    if (result.containsKey(index)) {
                        value += result.get(index);
                    }
                    result.put(index, value);
                }
            } else {
                int index = Integer.parseInt(temp[1]);
                double value = Double.parseDouble(temp[0].replace("x", ""));
                if (result.containsKey(index)) {
                    value += result.get(index);
                }
                result.put(index, value);
            }
        }
        return result;
    }

    /*
    * 加减计算
    * */
    private static String add(HashMap<Integer, Double> p1, HashMap<Integer, Double> p2, boolean add) {
        StringBuilder result = new StringBuilder();
        //如果是减法对p2进行取负数操作
        if (!add) {
            p2.replaceAll((i, v) -> -p2.get(i));
        }

        //对p2遍历，如果1中有进行相加，没有则自己
        for (int index : p2.keySet()) {
            double value = p1.getOrDefault(index, 0.0) + p2.get(index);
            //p1值取完后就移除，为了后面对只p1中有的index进行添加
            p1.remove(index);
            if (value != 0) result.append(value).append("x^").append(index).append("+");
        }

        //添加只有p1中有的index
        for (int index : p1.keySet()) {
            double value = p1.get(index);
            if (value != 0) result.append(value).append("x^").append(index).append("+");
        }

        //等于0的操作
        if (result.length() == 0) result.append("0 ");

        //优化后返回
        return result.delete(result.length() - 1, result.length()).toString().replace("+-", "-").replace("x^0", "").replace("^1", "");
    }

    private static String multiplication(HashMap<Integer, Double> p1, HashMap<Integer, Double> p2) {
        HashMap<Integer, Double> resultMap = new HashMap<>();
        StringBuilder result = new StringBuilder();

        for (int index1 : p1.keySet()) {
            for (int index2 : p2.keySet()) {
                double value = p1.get(index1) * p2.get(index2);
                if (resultMap.containsKey(index1 + index2)) {
                    value += resultMap.get(index1 + index2);
                }
                resultMap.put(index1 + index2, value);
            }
        }

        for (int index : resultMap.keySet()) {
            double value = resultMap.get(index);
            if (value != 0) result.append(value).append("x^").append(index).append("+");
        }

        //等于0的操作
        if (result.length() == 0) result.append("0 ");

        //优化后返回
        return result.delete(result.length() - 1, result.length()).toString().replace("+-", "-").replace("x^0", "").replace("^1", "");
    }

    /*
    * 多项式除法实现
    * */
    private static String div(HashMap<Integer, Double> p1, HashMap<Integer, Double> p2) {

        int maxIndexP1 = Collections.max(p1.keySet());
        int maxIndexP2 = Collections.max(p2.keySet());

        double[] a = new double[maxIndexP1 + 1];
        double[] b = new double[maxIndexP2 + 1];

        for (int i = maxIndexP1;i >= 0;i--) {
            a[i] = p1.getOrDefault(i, 0.0);
        }

        for (int i = maxIndexP2;i >= 0;i--) {
            b[i] = p2.getOrDefault(i, 0.0);
        }

        return polynomial_div(a, b, new double[a.length - b.length + 1], new double[b.length - 1]);

    }

    public static String polynomial_div(double[] a,double[] b,double[] r,double[] l){
        StringBuilder result = new StringBuilder();

        int na=a.length;
        int nb=b.length;
        int nr=r.length;    //10
        int nl=l.length;    //10
        int ta,tb;
        ta=na-1;
        for(int i=0;i<nr;i++){
            r[i]=0.0;
        }
        for(int i=nr;i>0;i--){
            r[i-1]=a[ta]/b[nb-1];
            tb=ta;
            for(int j=1;j<=nb-1;j++){
                a[tb-1]-=r[i-1]*b[nb-j-1];
                tb-=1;
            }
            ta-=1;
        }
        for(int i=0;i<nl;i++){
            l[i]=a[i];
        }

        result.append("商式：");
        for (int i = r.length - 1;i>=0;i--) {
            if (r[i] != 0) result.append(r[i]).append("x^").append(i).append("+");
        }

        result.delete(result.length() - 1, result.length()).append("\n").append("余式：");


        for (int i = l.length - 1;i>=0;i--) {
            if (l[i] != 0) result.append(l[i]).append("x^").append(i).append("+");
        }
        result.delete(result.length() - 1, result.length());
        return result.toString().replace("+-", "-").replace("x^0", "").replace("^1", "");
    }

}
